1. Field of the Invention
The present invention relates to an orthogonal transformation apparatus and an orthogonal transformation method that achieve two-dimensional orthogonal transformation performed by a block unit of m×n pixels (m and n are natural numbers: m=n, or m≠n) such as 8×8 pixels through breaking it down to one-dimensional orthogonal transformation of a row direction and of a column direction. Further, the present invention relates to an imaging system.
2. Description of the Related Art
Orthogonal transformation processing is the processing for transforming a signal on the spatial axis into a signal on the frequency axis. Particularly, discrete cosine transform (DCT) as a way of orthogonal transformation is employed in JPEG (Joint Photographic Experts Group) and MPEG (Moving Picture Experts Group) which are the typical compression techniques of pixels data, and it has been served widely as a technique capable of transferring data with small amount of information, in accordance with diffusion of digital cameras and digital video cameras, and developments in the digital communication technique.
FIG. 14 shows the structure of a typical image compression apparatus. The orthogonal transformation processing will be described hereinafter referring to this drawing. A DCT circuit 31 for performing discrete cosine transformation generates DCT coefficients by performing frequency transformation of pixel data that is inputted sequentially through being divided into blocks of 8×8 pieces in advance. Color change in a natural image is smooth in most cases. When frequency transformation is performed, large-valued DCT coefficients become concentrated in a low-frequency area m shown in FIG. 15, and small-valued DCT coefficients are distributed in a high-frequency area n. Then, a quantizer 32 generates quantization coefficients through dividing the above-described DCT coefficients by a quantization value that is set in advance. This processing allows “0” coefficient to be concentrated in the high-frequency area which does not influence the picture quality. Further, a variable-length encoder 33 generates run-length data by combining RUN that shows number of “0” in order of zigzag scan and LEVEL that shows magnitude of a coefficient value. Further, the variable-length encoder 33 reduces the data volume by allocating different length of code words in accordance with the appearance rate of the above-described combination.
Meanwhile, as shown in FIG. 16, an image expansion apparatus for decoding variable-length encoded data that is encoded by the above-described structure comprises a variable-length decoder 34, an inverse quantizer 35 and an inverse DCT circuit 36 in accord with the image compression apparatus described above. The variable-length decoder 34 decodes the inputted variable-length encoded data as a combination of RUN that indicates the number of “0” and LEVEL that indicates the magnitude of the coefficient values to generate “0” coefficients by the magnitude of RUN, and combines the “0” coefficients with the coefficient indicated by LEVEL. This operation is repeated until the coefficients by the 8×8 pixels are generated. The inverse quantizer 35 generates inverse-quantization DCT coefficients by multiplying the generated coefficients corresponding to the 8×8 pixels by a quantization value that is set in advance. Further, the inverse DCT circuit 36 decodes the encoded variable-length encoded data into pixel data by transforming the generated inverse quantization coefficient from the frequency area to the spatial area.
Next, FIG. 17 shows the structure of a typical encoder for moving picture. Hereinafter, the moving picture encoder will be described referring to this drawing. As a moving picture compression method, MPEG that is standardized by ISO (International Organization for Standardization) is known in general. MPEG performs encoding by utilizing intra-frame correlation or encoding by utilizing inter-frame correlation by each block of a screen (frame). A frame constituted by using only the intra-frame correlation is called an I (intra) picture, and a frame constituted under mixture of intra-frame correlation and inter-frame correlation is called a P (predictive) picture and a B (bidirectionally predictive) picture. For the I pictures, compression processing that is the same as the typical processing is performed. Thus, a part of the explanation thereof will be omitted below.
An output of the quantizer 32 is also inputted to the inverse quantizer 35, and it is sent thereafter to a reconstitution image generator 40 through the inverse DCT circuit 36. At the same time, an output (compensated result) of a motion compensator 42 is also inputted to the reconstitution image generator 40. When the output of the quantizer 32 is an output generated based on the block of the inter-frame correlation, both of the input data are added, and the result thereof is written to a frame memory 41. Meanwhile, since the I picture is constituted only with the intra-frame correlation, the output of the motion compensator 42 is not inputted to the reconstitution image generator 40. Therefore, the data transmitted from the inverse DCT circuit 36 is written as it is to the frame memory 41. Image data sent to the frame memory 41 in the manner described above is called a reconstituted image, and this reconstituted image is used as a reference image in generating a P picture or a B picture.
Next, a procedure for encoding the P picture will be described. Image data of a block unit (hereinafter, referred to as input image data (block)) is inputted from an input device 37, and it is sent to a differentiator 38 and a motion detector 43. The motion detector 43 reads out an pixel data group (hereinafter, referred to as a memory pixel data (block) group) located in the vicinity of the same spatial position as that of the input image data (block), from the frame memory 41, and performs a motion search. A motion search is performed through detecting the memory pixel data (block) that has the highest correlation with the input image data (block) from the memory pixel data (block) group. The motion detector 43 outputs the memory pixel data (block) having the highest correlation to the motion compensator 42 as a reference image. Further, the motion detector 43 outputs a motion vector, that indicates the position of the reference image, to a motion vector encoder 44. When intra-frame correlation encoding is selected, the encoding processing hereinafter is the same as that at the time of I picture. When inter-frame correlation encoding is selected, the reference image is sent to the differentiator 38 through the motion compensator 42. The differentiator 38 calculates a difference between the input image data (block) and the reference image, and outputs it to the DCT circuit 31. The variable-length encoder 33 encodes the quantized image data, and outputs the encoded data along with the data encoded by the motion vector encoder 44. FIG. 18 is a block diagram showing the structure of a typical image decoder that corresponds to the moving picture encoder shown in FIG. 17.
Hereinafter, a conventional two-dimensional discrete cosine transformation apparatus will be described. The two-dimensional DCT used for image processing is generally processed based on a unit of 8×8 pixels, and it is expressed by expression (1). It can be seen that one-dimensional DCT expressed by expression (2) is repeatedly executed in expression (1) in row and column directions. Thus, DCT may be performed by: executing one-dimensional DCT in the row direction; transposing the obtained result to commute the row and the column; executing the same one-dimensional DCT in the column direction; and return the row and the column to the original state in the obtained result. Further, inverse DCT is also expressed by expression (3), and it can be seen that one-dimensional inverse DCT expressed by expression (4) is repeatedly executed in the row and column directions. The inverse DCT can be achieved in the same manner as that of DCT.
                                          F            ⁡                          (                              u                ,                v                            )                                =                                    1              4                        ⁢            CuCv            ⁢                                          ∑                                  x                  =                  0                                7                            ⁢                                                ∑                                      y                    =                    0                                    7                                ⁢                                                      f                    ⁡                                          (                                              x                        ,                        y                                            )                                                        ⁢                  cos                                                                    ⁣                                  ⁢                                                            (                                                      2                    ⁢                    x                                    +                  1                                )                            ⁢              u              ⁢                                                          ⁢              π                        16                    ⁢          cos                ⁣                                  ⁢                                            (                                                2                  ⁢                  y                                +                1                            )                        ⁢            v            ⁢                                                  ⁢            π                    16                                    [                  Expression          ⁢                                          ⁢          1                ]                                                      F            ⁡                          (              u              )                                =                      Cu            ⁢                                          ∑                                  x                  =                  0                                7                            ⁢                                                f                  ⁡                                      (                    x                    )                                                  ⁢                cos                                                    ⁣                                            (                                                2                  ⁢                  x                                +                1                            )                        ⁢            u            ⁢                                                  ⁢            π                    16                                    [                  Expression          ⁢                                          ⁢          2                ]                                                      f            ⁡                          (                              x                ,                y                            )                                =                                    1              4                        ⁢                                          ∑                                  u                  =                  0                                7                            ⁢                                                ∑                                      v                    =                    0                                    7                                ⁢                                                      CuCvF                    ⁡                                          (                                              u                        ,                        v                                            )                                                        ⁢                  cos                                                                    ⁣                                  ⁢                                                            (                                                      2                    ⁢                    x                                    +                  1                                )                            ⁢              u              ⁢                                                          ⁢              π                        16                    ⁢          cos                ⁣                                  ⁢                                            (                                                2                  ⁢                  y                                +                1                            )                        ⁢            v            ⁢                                                  ⁢            π                    16                                    [                  Expression          ⁢                                          ⁢          3                ]                                                      f            ⁡                          (              x              )                                =                                    ∑                              u                =                0                            7                        ⁢                                          CuF                ⁡                                  (                  u                  )                                            ⁢              cos                                      ⁣                                            (                                                2                  ⁢                  x                                +                1                            )                        ⁢            u            ⁢                                                  ⁢            π                    16                                    [                  Expression          ⁢                                          ⁢          4                ]            
As the conventional DCT that performs the processing based on a block unit of 8×8 pixels, there is a discrete cosine transformation device disclosed in Japanese Published Patent Literature (Japanese Unexamined Patent Publication H5-153403). One of the examples will be described referring to FIG. 19. A one-dimensional DCT circuit 52 performs one-dimensional DCT by a unit of 8 pixels in one row on the image data that is inputted successively in the row direction from an input device 51. The result thereof is outputted to a transposition data buffer 53 and stored therein. After repeating the above-described operation by eight rows, the data is read out in the row direction from the transposition data buffer 53, and the readout data is outputted to a one-dimensional DCT circuit 54. The one-dimensional DCT circuit 54 performs one-dimensional DCT processing by a unit of 8 pixels in one column, and the processed result is outputted to an output device 55.
However, it is difficult to achieve more speeding-up in the structure of the conventional technique described above. That is, the power consumption is increased when the operation is sped up. Further, a plurality of memory devices (transposition data buffers) is also required when a plurality of DCT circuits is provided in parallel, which expands the circuit scale.